//https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/?envType=daily-question&envId=2023-09-17


class Solution {
public:
    int maximumSum(vector<int>& arr) 
    {
        int n = arr.size(), ans = arr[0];
        vector<int> left(n), right(n);
        left[0] = arr[0];
        right[n - 1] = arr[n - 1];
        for(int i = 1; i < n; i++) 
        {
            right[n - 1 - i] = max(right[n - i] + arr[n - 1 - i], arr[n - 1 - i]);
            left[i] = max(left[i - 1] + arr[i], arr[i]);
            ans = max(ans, left[i]);
        }
        for(int i = 1; i < n - 1; i++)
        {
            ans = max(ans, left[i - 1] + right[i + 1]);
        }
        return ans;
    }
};